package com.zrf.base.knowledge.collections;

import java.io.ObjectInputStream;
import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.SortedMap;
import java.util.Spliterator;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

/**
 * 自己实现treeMap
 *
 * @author zhouruifeng
 *         create at 2017/6/4.
 */
public class MyTreeMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
    /**
     * 红黑树节点的颜色 红色
     */
    private static final boolean RED = false;
    /**
     * 红黑树节点的颜色 黑色
     */
    private static final boolean BLACK = true;
    /**
     * 比较器
     */
    private final Comparator<? super K> comparator;
    /**
     * 根节点
     */
    private transient Entry<K, V> root;
    /**
     * map的大小
     */
    private transient int size = 0;

    private transient MyTreeMap.EntrySet entrySet;

    /**
     * 无参构造方法
     */
    public MyTreeMap() {
        comparator = null;
    }

    /**
     * 比较器构造方法
     *
     * @param comparator
     */
    public MyTreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    public MyTreeMap(Map<? extends K, ? extends V> m) {
        this.comparator = null;
        putAll(m);
    }

    public MyTreeMap(SortedMap<K, ? extends V> sortedMap) {
        this.comparator = sortedMap.comparator();
    }

    @Override
    public Set<Map.Entry<K,V>> entrySet() {
        MyTreeMap.EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new MyTreeMap.EntrySet());
    }

    @Override
    public V put(K key, V value) {
        MyTreeMap.Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new MyTreeMap.Entry(key, value, null);
            size = 1;
            return null;
        }
        int cmp;
        MyTreeMap.Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0) {
                    t = t.left;
                } else if (cmp > 0) {
                    t = t.right;
                } else {
                    return t.setValue(value);
                }
            } while (t != null);
        }
        else {
            if (key == null) {
                throw new NullPointerException();
            }
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0) {
                    t = t.left;
                } else if (cmp > 0) {
                    t = t.right;
                } else {
                    return t.setValue(value);
                }
            } while (t != null);
        }
        MyTreeMap.Entry<K,V> e = new MyTreeMap.Entry<>(key, value, parent);
        if (cmp < 0) {
            parent.left = e;
        } else {
            parent.right = e;
        }
        fixAfterInsertion(e);
        size++;
        return null;
    }

    @Override
    public void putAll(Map m) {
        int mapSize = m.size();
        if (size == 0 && mapSize != 0 && m instanceof SortedMap) {
            Comparator<?> c = ((SortedMap<?, ?>) m).comparator();
            if (c == comparator || (c != null && c.equals(comparator))) {
                try {
                    initBuildFromSorted(mapSize, m.entrySet().iterator(),
                            null, null);
                } catch (java.io.IOException cannotHappen) {
                } catch (ClassNotFoundException cannotHappen) {
                }
                return;
            }
        }
        super.putAll(m);
    }

    @Override
    public Object getOrDefault(Object key, Object defaultValue) {
        return null;
    }

    @Override
    public void forEach(BiConsumer action) {

    }

    @Override
    public void replaceAll(BiFunction function) {

    }

    @Override
    public Object putIfAbsent(Object key, Object value) {
        return null;
    }

    @Override
    public boolean remove(Object key, Object value) {
        return false;
    }

    @Override
    public boolean replace(Object key, Object oldValue, Object newValue) {
        return false;
    }

    @Override
    public Object replace(Object key, Object value) {
        return null;
    }

    @Override
    public Object computeIfAbsent(Object key, Function mappingFunction) {
        return null;
    }

    @Override
    public Object computeIfPresent(Object key, BiFunction remappingFunction) {
        return null;
    }

    @Override
    public Object compute(Object key, BiFunction remappingFunction) {
        return null;
    }

    @Override
    public Object merge(Object key, Object value, BiFunction remappingFunction) {
        return null;
    }

    /**
     * 初始化构建map根据有序的iterator
     *
     * @param size       iterator的size
     * @param iterator   iterator
     * @param str
     * @param defaultVal 默认的值
     * @throws java.io.IOException
     * @throws ClassNotFoundException
     */
    private void initBuildFromSorted(int size, Iterator<?> iterator, ObjectInputStream str, V defaultVal)
            throws java.io.IOException, ClassNotFoundException {
        this.size = size;
        root = initBuildFromSorted(0, 0, size - 1, computeRedLevel(size),
                iterator, str, defaultVal);
    }

    /**
     * @param level      在当前树的d第几级
     * @param low        需要插入的节点的start
     * @param high       需要插入的end节点的index
     * @param redLevel
     * @param iterator   需要插入的数据的iterator
     * @param str        if iterator为空从str中获取key and value
     * @param defaultVal 默认的值
     * @return
     * @throws java.io.IOException
     * @throws ClassNotFoundException
     */
    private MyTreeMap.Entry<K, V> initBuildFromSorted(int level, int low, int high, int redLevel, Iterator<?> iterator,
                                                      ObjectInputStream str, V defaultVal)
            throws java.io.IOException, ClassNotFoundException {
        if (high < low) {
            return null;
        }

        int middleIndex = (low + high) >>> 1;


        MyTreeMap.Entry<K, V> left = null;
        if (low < middleIndex) {
            left = initBuildFromSorted(level + 1, low, middleIndex - 1, redLevel, iterator, str, defaultVal);
        }

        // extract key and/or value from iterator or stream
        K key;
        V value;
        if (iterator != null) {
            if (defaultVal == null) {
                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) iterator.next();
                key = (K) entry.getKey();
                value = (V) entry.getValue();
            } else {
                key = (K) iterator.next();
                value = defaultVal;
            }
        } else { // use stream
            key = (K) str.readObject();
            value = (defaultVal != null ? defaultVal : (V) str.readObject());
        }
        MyTreeMap.Entry<K, V> middle = new MyTreeMap.Entry<>(key, value, null);

        // color nodes in non-full bottommost level red
        if (level == redLevel)
            middle.color = RED;

        if (left != null) {
            middle.left = left;
            left.parent = middle;
        }

        if (middleIndex < high) {
            MyTreeMap.Entry<K, V> right = initBuildFromSorted(level + 1, middleIndex + 1, high, redLevel,
                    iterator, str, defaultVal);
            middle.right = right;
            right.parent = middle;
        }

        return middle;
    }

    /** From CLR */
    private void fixAfterInsertion(MyTreeMap.Entry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                /**
                 **********g
                 ******f****
                 **x*******x
                 */
                MyTreeMap.Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                MyTreeMap.Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

    /**
     * Delete node p, and then rebalance the tree.
     */
    private void deleteEntry(MyTreeMap.Entry<K,V> p) {
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            MyTreeMap.Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        MyTreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null) {
                root = replacement;
            } else if (p == p.parent.left) {
                p.parent.left = replacement;
            } else {
                p.parent.right = replacement;
            }
            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK) {
                fixAfterDeletion(replacement);
            }
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

    /** From CLR */
    private void fixAfterDeletion(MyTreeMap.Entry<K,V> x) {
        while (x != root && colorOf(x) == BLACK) {
            if (x == leftOf(parentOf(x))) {
                MyTreeMap.Entry<K,V> sib = rightOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(parentOf(x));
                    sib = rightOf(parentOf(x));
                }

                if (colorOf(leftOf(sib))  == BLACK &&
                        colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(parentOf(x));
                    x = root;
                }
            } else { // symmetric
                MyTreeMap.Entry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                        colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }

        setColor(x, BLACK);
    }

    /**
     * From CLR
     * 树坐旋转
     */
    private void rotateLeft(MyTreeMap.Entry<K,V> p) {
        if (p != null) {
            MyTreeMap.Entry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

    /** From CLR */
    private void rotateRight(MyTreeMap.Entry<K,V> p) {
        if (p != null) {
            MyTreeMap.Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }


    private static int computeRedLevel(int sz) {
        int level = 0;
        for (int m = sz - 1; m >= 0; m = m / 2 - 1) {
            level++;
        }
        return level;
    }

    /**
     * Returns the successor of the specified Entry, or null if no such.
     */
    static <K, V> MyTreeMap.Entry<K, V> successor(MyTreeMap.Entry<K, V> t) {
        if (t == null) {
            return null;
        } else if (t.right != null) {
            MyTreeMap.Entry<K, V> p = t.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        } else {
            MyTreeMap.Entry<K, V> p = t.parent;
            MyTreeMap.Entry<K, V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    /**
     * Returns the predecessor of the specified Entry, or null if no such.
     */
    static <K, V> MyTreeMap.Entry<K, V> predecessor(MyTreeMap.Entry<K, V> t) {
        if (t == null) {
            return null;
        } else if (t.left != null) {
            MyTreeMap.Entry<K, V> p = t.left;
            while (p.right != null) {
                p = p.right;
            }
            return p;
        } else {
            MyTreeMap.Entry<K, V> p = t.parent;
            MyTreeMap.Entry<K, V> ch = t;
            while (p != null && ch == p.left) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

    private static <K, V> boolean colorOf(MyTreeMap.Entry<K, V> p) {
        return p == null ? BLACK : p.color;
    }

    private static <K, V> MyTreeMap.Entry<K, V> parentOf(MyTreeMap.Entry<K, V> p) {
        return p == null ? null : p.parent;
    }

    private static <K, V> void setColor(MyTreeMap.Entry<K, V> p, boolean c) {
        if (p != null) {
            p.color = c;
        }
    }

    private static <K, V> MyTreeMap.Entry<K, V> leftOf(MyTreeMap.Entry<K, V> p) {
        return (p == null) ? null : p.left;
    }

    private static <K, V> MyTreeMap.Entry<K, V> rightOf(MyTreeMap.Entry<K, V> p) {
        return (p == null) ? null : p.right;
    }

    /**
     * Returns the first Entry in the TreeMap (according to the TreeMap's
     * key-sort function).  Returns null if the TreeMap is empty.
     */
    final MyTreeMap.Entry<K, V> getFirstEntry() {
        MyTreeMap.Entry<K, V> p = root;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
        }
        return p;
    }

    /**
     * Returns the last Entry in the TreeMap (according to the TreeMap's
     * key-sort function).  Returns null if the TreeMap is empty.
     */
    final MyTreeMap.Entry<K, V> getLastEntry() {
        MyTreeMap.Entry<K, V> p = root;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
        }
        return p;
    }

    /**
     * Version of getEntry using comparator. Split off from getEntry
     * for performance. (This is not worth doing for most methods,
     * that are less dependent on comparator performance, but is
     * worthwhile here.)
     */
    final MyTreeMap.Entry<K, V> getEntryUsingComparator(Object key) {
        K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            MyTreeMap.Entry<K, V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0) {
                    p = p.left;
                } else if (cmp > 0) {
                    p = p.right;
                } else {
                    return p;
                }
            }
        }
        return null;
    }

    /**
     * Returns this map's entry for the given key, or {@code null} if the map
     * does not contain an entry for the key.
     *
     * @return this map's entry for the given key, or {@code null} if the map
     * does not contain an entry for the key
     * @throws ClassCastException   if the specified key cannot be compared
     *                              with the keys currently in the map
     * @throws NullPointerException if the specified key is null
     *                              and this map uses natural ordering, or its comparator
     *                              does not permit null keys
     */
    final MyTreeMap.Entry<K, V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null) {
            return getEntryUsingComparator(key);
        }
        if (key == null) {
            throw new NullPointerException();
        }
        Comparable<? super K> k = (Comparable<? super K>) key;
        MyTreeMap.Entry<K, V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0) {
                p = p.left;
            } else if (cmp > 0) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    /**
     * Compares two keys using the correct comparison method for this TreeMap.
     */
    @SuppressWarnings("unchecked")
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
                : comparator.compare((K)k1, (K)k2);
    }


    /**
     * treeMap中每个节点
     *
     * @param <K> key
     * @param <V> value
     */
    static final class Entry<K, V> implements Map.Entry<K, V> {
        /**
         * key
         */
        private K key;
        /**
         * value
         */
        private V value;
        /**
         * 左子树
         */
        private Entry<K, V> left;
        /**
         * 右子树
         */
        private Entry<K, V> right;
        /**
         * 父节点
         */
        private Entry<K, V> parent;
        /**
         * 当前节点的颜色
         */
        private boolean color = BLACK;

        /**
         * 构造方法
         *
         * @param key    key
         * @param value  value
         * @param parent parent
         */
        Entry(K key, V value, Entry<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        /**
         * get key
         *
         * @return
         */
        public K getKey() {
            return key;
        }

        /**
         * get value
         *
         * @return
         */
        public V getValue() {
            return value;
        }

        /**
         * set new value return old value
         *
         * @param value
         * @return
         */
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;

            return Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue());
        }

        public int hashCode() {
            int keyHash = key == null ? 0 : key.hashCode();
            int valueHash = value == null ? 0 : value.hashCode();
            return keyHash ^ valueHash;
        }

        public String toString() {
            return key + "=" + value;
        }
    }

    class EntrySet extends AbstractSet<Map.Entry<K, V>> {
        public Iterator<Map.Entry<K, V>> iterator() {
            return new MyTreeMap.EntryIterator(getFirstEntry());
        }

        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
            Object value = entry.getValue();
            MyTreeMap.Entry<K, V> p = getEntry(entry.getKey());
            return p != null && Objects.equals(p.getValue(), value);
        }

        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
            Object value = entry.getValue();
            MyTreeMap.Entry<K,V> p = getEntry(entry.getKey());
            if (p != null && Objects.equals(p.getValue(), value)) {
                deleteEntry(p);
                return true;
            }
            return false;
        }

        public int size() {
            return MyTreeMap.this.size();
        }

        public void clear() {
            MyTreeMap.this.clear();
        }

        public Spliterator<Map.Entry<K,V>> spliterator() {
            return new MyTreeMap.EntrySpliterator<K,V>(MyTreeMap.this, null, null, 0, -1);
        }
    }

    final class EntryIterator extends MyTreeMap.PrivateEntryIterator {
        EntryIterator(MyTreeMap.Entry<K,V> first) {
            super(first);
        }

        public Map.Entry<K, V> next() {
            return nextEntry();
        }
    }

    final class ValueIterator extends MyTreeMap.PrivateEntryIterator {
        ValueIterator(MyTreeMap.Entry<K,V> first) {
            super(first);
        }
        public V next() {
            return (V) nextEntry().value;
        }
    }

    final class KeyIterator extends MyTreeMap.PrivateEntryIterator {
        KeyIterator(MyTreeMap.Entry<K,V> first) {
            super(first);
        }
        public K next() {
            return (K) nextEntry().key;
        }
    }

    /**
     * Base class for TreeMap Iterators
     */
    abstract class PrivateEntryIterator<T> implements Iterator<T> {
        MyTreeMap.Entry<K, V> next;
        MyTreeMap.Entry<K, V> lastReturned;

        PrivateEntryIterator(MyTreeMap.Entry<K, V> first) {
            lastReturned = null;
            next = first;
        }

        public final boolean hasNext() {
            return next != null;
        }

        final MyTreeMap.Entry<K, V> nextEntry() {
            MyTreeMap.Entry<K, V> e = next;
            if (e == null) {
                throw new NoSuchElementException();
            }
            next = successor(e);
            lastReturned = e;
            return e;
        }

        final MyTreeMap.Entry<K, V> prevEntry() {
            MyTreeMap.Entry<K, V> e = next;
            if (e == null) {
                throw new NoSuchElementException();
            }
            next = predecessor(e);
            lastReturned = e;
            return e;
        }

        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            // deleted entries are replaced by their successors
            if (lastReturned.left != null && lastReturned.right != null)
                next = lastReturned;
            deleteEntry(lastReturned);
            lastReturned = null;
        }
    }

    /**
     * Base class for spliterators.  Iteration starts at a given
     * origin and continues up to but not including a given fence (or
     * null for end).  At top-level, for ascending cases, the first
     * split uses the root as left-fence/right-origin. From there,
     * right-hand splits replace the current fence with its left
     * child, also serving as origin for the split-off spliterator.
     * Left-hands are symmetric. Descending versions place the origin
     * at the end and invert ascending split rules.  This base class
     * is non-commital about directionality, or whether the top-level
     * spliterator covers the whole tree. This means that the actual
     * split mechanics are located in subclasses. Some of the subclass
     * trySplit methods are identical (except for return types), but
     * not nicely factorable.
     *
     * Currently, subclass versions exist only for the full map
     * (including descending keys via its descendingMap).  Others are
     * possible but currently not worthwhile because submaps require
     * O(n) computations to determine size, which substantially limits
     * potential speed-ups of using custom Spliterators versus default
     * mechanics.
     *
     * To boostrap initialization, external constructors use
     * negative size estimates: -1 for ascend, -2 for descend.
     */
    static class TreeMapSpliterator<K,V> {
        final MyTreeMap<K,V> tree;
        MyTreeMap.Entry<K,V> current; // traverser; initially first node in range
        MyTreeMap.Entry<K,V> fence;   // one past last, or null
        int side;                   // 0: top, -1: is a left split, +1: right
        int est;                    // size estimate (exact only for top-level)

        TreeMapSpliterator(MyTreeMap<K,V> tree,
                           MyTreeMap.Entry<K,V> origin, MyTreeMap.Entry<K,V> fence,
                           int side, int est) {
            this.tree = tree;
            this.current = origin;
            this.fence = fence;
            this.side = side;
            this.est = est;
        }

        final int getEstimate() { // force initialization
            int s;
            MyTreeMap<K, V> t;
            if ((s = est) < 0) {
                if ((t = tree) != null) {
                    current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
                    s = est = t.size;
                } else {
                    s = est = 0;
                }
            }
            return s;
        }

        public final long estimateSize() {
            return (long)getEstimate();
        }
    }

    static final class EntrySpliterator<K,V> extends MyTreeMap.TreeMapSpliterator<K,V>
            implements Spliterator<Map.Entry<K,V>> {
        EntrySpliterator(MyTreeMap<K,V> tree,
                         MyTreeMap.Entry<K,V> origin, MyTreeMap.Entry<K,V> fence,
                         int side, int est) {
            super(tree, origin, fence, side, est);
        }

        public MyTreeMap.EntrySpliterator<K,V> trySplit() {
            if (est < 0)
                getEstimate(); // force initialization
            int d = side;
            MyTreeMap.Entry<K,V> e = current, f = fence,
                    s = ((e == null || e == f) ? null :      // empty
                            (d == 0)              ? tree.root : // was top
                                    (d >  0)              ? e.right :   // was right
                                            (d <  0 && f != null) ? f.left :    // was left
                                                    null);
            if (s != null && s != e && s != f &&
                    tree.compare(e.key, s.key) < 0) {        // e not already past s
                side = 1;
                return new MyTreeMap.EntrySpliterator<>
                        (tree, e, current = s, -1, est >>>= 1);
            }
            return null;
        }

        public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
            if (action == null)
                throw new NullPointerException();
            if (est < 0)
                getEstimate(); // force initialization
            MyTreeMap.Entry<K,V> f = fence, e, p, pl;
            if ((e = current) != null && e != f) {
                current = f; // exhaust
                do {
                    action.accept(e);
                    if ((p = e.right) != null) {
                        while ((pl = p.left) != null)
                            p = pl;
                    } else {
                        while ((p = e.parent) != null && e == p.right)
                            e = p;
                    }
                } while ((e = p) != null && e != f);
            }
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
            MyTreeMap.Entry<K,V> e;
            if (action == null)
                throw new NullPointerException();
            if (est < 0)
                getEstimate(); // force initialization
            if ((e = current) == null || e == fence)
                return false;
            current = successor(e);
            action.accept(e);
            return true;
        }

        public int characteristics() {
            return (side == 0 ? Spliterator.SIZED : 0) |
                    Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
        }

        @Override
        public Comparator<Map.Entry<K, V>> getComparator() {
            // Adapt or create a key-based comparator
            if (tree.comparator != null) {
                return Map.Entry.comparingByKey(tree.comparator);
            } else {
                return (Comparator<Map.Entry<K, V>> & Serializable) (e1, e2) -> {
                    @SuppressWarnings("unchecked")
                    Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
                    return k1.compareTo(e2.getKey());
                };
            }
        }
    }
}
